import java.util.Arrays;

public class Test {
}
class Solution {
    public long waysToBuyPensPencils(int total, int cost1, int cost2) {
        long count = 0;
        int n = total/cost1;
        for(int i=0; i<n+1; i++){
            count += (total/cost2+1);
            total -= cost1;
            if(total<0) break;
        }
        return count;
    }
}
class Solution1 {
    /**
     j: 和为j
     dp[j]: 和为j有多少种组合
     dp[j] += dp[j-nums[i]];
     拓展：小乐乐走台阶问题进阶版，一次可以走n步时，我们可以用完全背包解决，
     这里的n就相当于这道题的数组nums，台阶总数 = target!!!
     */
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int j=1; j<target+1; j++){
            for(int i=0; i<nums.length; i++){
                if(j >= nums[i])
                    dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}
class Solution2 {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0) return 0;
        int[] dp = new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE-1);
        dp[0] = 0;
        System.out.println(Arrays.toString(dp));
        for(int i=0; i<coins.length; i++){
            for(int j=coins[i]; j<amount+1; j++){
                if(j>=coins[i])
                    dp[j] = Math.min(dp[j-coins[i]]+1,dp[j]);
            }
        }
        return dp[amount]==Integer.MAX_VALUE-1?-1:dp[amount];
    }
}